class StreamChecker
{
public:
    StreamChecker(vector<string> &words)
    {
        this->trie = TrieNode();
        for (string &word : words)
        {
            TrieNode *t = &this->trie;
            for (int i = word.size() - 1; i >= 0; --i)
            {
                if (!t->children.count(word[i]))
                {
                    t->children[word[i]] = new TrieNode();
                }
                t = t->children[word[i]];
            }
            t->endCount += 1;
        }
        this->stream.reserve(100000);
    }

    bool query(char letter)
    {
        this->stream.push_back(letter);
        TrieNode *t = &this->trie;
        for (int i = this->stream.size() - 1; i >= 0; --i)
        {
            if (t->endCount)
            {
                return true;
            }
            if (t->children.count(this->stream[i]))
            {
                t = t->children[this->stream[i]];
            }
            else
            {
                return false;
            }
        }
        return t->endCount;
    }

    struct TrieNode
    {
        int endCount = 0;
        unordered_map<char, TrieNode *> children;
        ~TrieNode()
        {
            for (auto &[_, pChild] : children)
            {
                delete pChild;
                pChild = nullptr;
            }
        }
    };

private:
    TrieNode trie;
    string stream;
};

/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */